package Top200;

/**
 * @author zhangmin
 * @create 2022-02-22 9:34
 * 使用数组作为原地的哈希表，先将数组中负数变为n+1，然后遍历的时候将遍历到的数作为下标的位置变为负数
 */
public class firstMissingPositive41 {
    public int firstMissingPositive(int[] nums) {
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i]<=0){
                nums[i]=n+1;
            }
        }
        for (int i = 0; i < n; i++) {
            //有可能会找的重复的位置，已经变为负数了
            int num=Math.abs(nums[i]);
            if (num<=n){
                nums[num-1]=-Math.abs(nums[num-1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i]>0){
                return i+1;
            }
        }
        return n+1;
    }
}
